package LeetCode.leetcode74;

class Solution {
    public static void main(String[] args) {
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        System.out.println(new Solution().searchMatrix(matrix,3));
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        return searchMatrix2(matrix,target,0, matrix.length-1,matrix[0].length-1);
    }
    public boolean searchMatrix2(int[][] matrix, int target, int l, int r, int col) {
        if (l > r) return false;
        int m = (l+r)/2;
        if (matrix[m][0] <= target && target <= matrix[m][col]){
            int left = 0, right = col;
            while (left <= right){
                int mid = left + (right - left)/2;
                if (target == matrix[m][mid]){
                    return true;
                }else if (target < matrix[m][mid]){
                    right = mid - 1;
                }else if (target > matrix[m][mid]){
                    left = mid + 1;
                }
            }
            return  false;
        }else if (matrix[m][col] < target){
            return searchMatrix2(matrix,target,m+1,r,col);
        }else{
            return searchMatrix2(matrix,target,l, m - 1, col);
        }
    }
}